package com.zys.el.user.util.FPGrowth;

import org.springframework.stereotype.Component;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

@Component
public class Myfptree2 {
    public static final int support = 2; // 设定最小支持频次为2
    public static final double CONFIDENCE = 0.4;

    private List<String> tm;
    private List<List<String>> re;

    public List<List<String>> getRe() {
        return re;
    }

    public void setRe(List<List<String>> re) {
        this.re = re;
    }

    //保存第一次的次序
    public Map<String, Integer> ordermap = new HashMap<String, Integer>();

    public LinkedList<LinkedList<String>> readF1(String filePath) throws IOException {
        LinkedList<LinkedList<String>> records = new LinkedList<LinkedList<String>>();
        String path = filePath;
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));

        for (String line = br.readLine(); line != null; line = br.readLine()) {
            if (line.length() == 0 || "".equals(line)) continue;
            String[] str = line.split(",");
            LinkedList<String> litm = new LinkedList<String>();
            for (int i = 0; i < str.length; i++) {
                litm.add(str[i].trim());
            }
            records.add(litm);
        }
        br.close();
        return records;
    }

    //创建表头链
    public LinkedList<TreeNode2> buildHeaderLink(LinkedList<LinkedList<String>> records) {
        LinkedList<TreeNode2> header = null;
        if (records.size() > 0) {
            header = new LinkedList<TreeNode2>();
        } else {
            return null;
        }
        Map<String, TreeNode2> map = new HashMap<String, TreeNode2>();
        for (LinkedList<String> items : records) {

            for (String item : items) {
                //如果存在数量增1，不存在则新增
                if (map.containsKey(item)) {
                    map.get(item).Sum(1);
                } else {
                    TreeNode2 node = new TreeNode2();
                    node.setName(item);
                    node.setCount(1);
                    map.put(item, node);
                }
            }
        }
        // 把支持度大于（或等于）minSup的项加入到F1中
        Set<String> names = map.keySet();
        for (String name : names) {
            TreeNode2 tnode = map.get(name);
            if (tnode.getCount() >= support) {
                header.add(tnode);
            }
        }
        sort(header);

        String test = "ddd";
        return header;
    }

    //选择法排序,如果次数相等，则按名字排序,字典顺序,先小写后大写
    public List<TreeNode2> sort(List<TreeNode2> list) {
        int len = list.size();
        for (int i = 0; i < len; i++) {

            for (int j = i + 1; j < len; j++) {
                TreeNode2 node1 = list.get(i);
                TreeNode2 node2 = list.get(j);
                if (node1.getCount() < node2.getCount()) {
                    TreeNode2 tmp = new TreeNode2();
                    tmp = node2;
                    list.remove(j);
                    //list指定位置插入，原来的>=j元素都会往下移，不会删除,所以插入前要删除掉原来的元素
                    list.add(j, node1);
                    list.remove(i);
                    list.add(i, tmp);
                }
                //如果次数相等，则按名字排序,字典顺序,先小写后大写
                if (node1.getCount() == node2.getCount()) {
                    String name1 = node1.getName();
                    String name2 = node2.getName();
                    int flag = name1.compareTo(name2);
                    if (flag > 0) {
                        TreeNode2 tmp = new TreeNode2();
                        tmp = node2;
                        list.remove(j);
                        //list指定位置插入，原来的>=j元素都会往下移，不会删除,所以插入前要删除掉原来的元素
                        list.add(j, node1);
                        list.remove(i);
                        list.add(i, tmp);
                    }


                }
            }
        }

        return list;
    }

    //选择法排序，降序,如果同名按L 中的次序排序
    public List<String> itemsort(LinkedList<String> lis, List<TreeNode2> header) {
        //List<String> list=new ArrayList<String>();
        //选择法排序
        int len = lis.size();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                String key1 = lis.get(i);
                String key2 = lis.get(j);
                Integer value1 = findcountByname(key1, header);
                if (value1 == -1) continue;
                Integer value2 = findcountByname(key2, header);
                if (value2 == -1) continue;
                if (value1 < value2) {
                    String tmp = key2;
                    lis.remove(j);
                    lis.add(j, key1);
                    lis.remove(i);
                    lis.add(i, tmp);
                }
                if (value1 == value2) {
                    int v1 = ordermap.get(key1);
                    int v2 = ordermap.get(key2);
                    if (v1 > v2) {
                        String tmp = key2;
                        lis.remove(j);
                        lis.add(j, key1);
                        lis.remove(i);
                        lis.add(i, tmp);
                    }
                }
            }
        }
        return lis;
    }

    public Integer findcountByname(String itemname, List<TreeNode2> header) {
        Integer count = -1;
        for (TreeNode2 node : header) {
            if (node.getName().equals(itemname)) {
                count = node.getCount();
            }
        }
        return count;
    }

    /**
     * @param records 构建树的记录,如I1,I2,I3
     * @param header
     * @return 返回构建好的树
     */
    public TreeNode2 builderFpTree(LinkedList<LinkedList<String>> records, List<TreeNode2> header) {

        TreeNode2 root;
        if (records.size() <= 0) {
            return null;
        }
        root = new TreeNode2();
        for (LinkedList<String> items : records) {
            itemsort(items, header);
            addNode(root, items, header);
        }
        String dd = "dd";
        String test = dd;
        return root;
    }

    //当已经有分枝存在的时候，判断新来的节点是否属于该分枝的某个节点，或全部重合，递归
    public TreeNode2 addNode(TreeNode2 root, LinkedList<String> items, List<TreeNode2> header) {
        if (items.size() <= 0) return null;
        String item = items.poll();
        //当前节点的孩子节点不包含该节点，那么另外创建一支分支。
        TreeNode2 node = root.findChild(item);
        if (node == null) {
            node = new TreeNode2();
            node.setName(item);
            node.setCount(1);
            node.setParent(root);
            root.addChild(node);

            //加将各个节点加到链头中
            for (TreeNode2 head : header) {
                if (head.getName().equals(item)) {
                    while (head.getNextHomonym() != null) {
                        head = head.getNextHomonym();
                    }
                    head.setNextHomonym(node);
                    break;
                }
            }
            //加将各个节点加到链头中
        } else {
            node.setCount(node.getCount() + 1);
        }

        addNode(node, items, header);
        return root;
    }

    //从叶子找到根节点，递归之
    public void toroot(TreeNode2 node, LinkedList<String> newrecord) {
        if (node.getParent() == null) return;
        String name = node.getName();
        newrecord.add(name);
        toroot(node.getParent(), newrecord);
    }

    //对条件FP-tree树进行组合，以求出频繁项集
    public void combineItem(TreeNode2 node, LinkedList<String> newrecord, String Item) {
        if (node.getParent() == null) return;
        String name = node.getName();
        newrecord.add(name);
        toroot(node.getParent(), newrecord);
    }


    //fp-growth
    public void fpgrowth(LinkedList<LinkedList<String>> records, List<String> item) {
        //保存新的条件模式基的各个记录，以重新构造FP-tree
        LinkedList<LinkedList<String>> newrecords = new LinkedList<LinkedList<String>>();
        //构建链头
        LinkedList<TreeNode2> header = buildHeaderLink(records);
        //创建FP-Tree
        TreeNode2 fptree = builderFpTree(records, header);
        //结束递归的条件
        if (header.size() <= 0 || fptree == null) {
            return;
        }
        //打印结果,输出频繁项集
        if (item != null) {
            //寻找条件模式基,从链尾开始
            for (int i = header.size() - 1; i >= 0; i--) {
                TreeNode2 head = header.get(i);
                String itemname = head.getName();
                Integer count = 0;
                while (head.getNextHomonym() != null) {
                    head = head.getNextHomonym();
                    //叶子count等于多少，就算多少条记录
                    count = count + head.getCount();

                }
                tm = new ArrayList<>();
                tm.addAll(item);
                tm.add(head.getName());
                tm.add(count.toString());
                re.add(tm);
                //打印频繁项集
//                System.out.println(head.getName() + "," + item + "\t" + count);
            }
        }
        //寻找条件模式基,从链尾开始
        for (int i = header.size() - 1; i >= 0; i--) {
            TreeNode2 head = header.get(i);
            List<String> itemname = new ArrayList<>();
            //再组合
            if (item == null) {
                itemname.add(head.getName());
            } else {
                item.add(head.getName());
                itemname = item;
            }

            while (head.getNextHomonym() != null) {
                head = head.getNextHomonym();
                //叶子count等于多少，就算多少条记录
                Integer count = head.getCount();
                for (int n = 0; n < count; n++) {
                    LinkedList<String> record = new LinkedList<String>();
                    toroot(head.getParent(), record);
                    newrecords.add(record);
                }
            }
            //System.out.println("-----------------");
            //递归之,以求子FP-Tree
            fpgrowth(newrecords, itemname);
        }
    }

    //保存次序，此步也可以省略，为了减少再加工结果的麻烦而加
    public void orderF1(LinkedList<TreeNode2> orderheader) {
        for (int i = 0; i < orderheader.size(); i++) {
            TreeNode2 node = orderheader.get(i);
            ordermap.put(node.getName(), i);
        }

    }


    //得到频繁1项集
    private Map<String, Integer> getItem1FC(List<List<String>> transList) {
        Map<String, Integer> sItem1FcMap = new HashMap<String, Integer>();
        Map<String, Integer> rItem1FcMap = new HashMap<String, Integer>();// 频繁1项集

        for (List<String> trans : transList) {
            for (String item : trans) {
                Integer count = sItem1FcMap.get(item);
                if (count == null) {
                    sItem1FcMap.put(item, 1);
                } else {
                    sItem1FcMap.put(item, count + 1);
                }
            }
        }

        Set<String> keySet = sItem1FcMap.keySet();
        for (String key : keySet) {
            Integer count = sItem1FcMap.get(key);
            if (count >= support) {
                rItem1FcMap.put(key, count);
            }
        }
        return rItem1FcMap;
    }


    //传入数据返回频繁项集，每一行的最后元素为频率

    /**
     * @param prerecords 二维数据
     * @param ownTasks   存在任务列表
     * @return
     */
    public Set<String> FPTreeLL(List<List<String>> prerecords, List<String> ownTasks) {
        //处理LinkedList
        LinkedList<LinkedList<String>> records = new LinkedList<>();
        for (int i = 0; i < prerecords.size(); i++) {
            records.add(new LinkedList<>());
            for (int j = 0; j < prerecords.get(i).size(); j++) {
                records.get(i).add(prerecords.get(i).get(j));
            }
        }

        List<List<String>> re = new ArrayList<>();
        this.setRe(re);

        LinkedList<TreeNode2> orderheader = this.buildHeaderLink(records);

        this.orderF1(orderheader);
        this.fpgrowth(records, null);

        List<List<String>> ll = this.getRe();

        int size = ll.size();
        Map<String, Integer> item1FC = this.getItem1FC(prerecords);
        int c = 1;
        for (String s : item1FC.keySet()) {
            ll.add(new ArrayList<>());
            ll.get(size - 1 + c).add(s);
            ll.get(size - 1 + c).add(item1FC.get(s).toString());
            c++;
        }
        System.out.println("ll" + ll);//目前的ll拿到服从支持度的项
        Map<List<String>, Integer> temp = new HashMap<>();
        for (int i = 0; i < ll.size(); i++) {
            temp.put(ll.get(i).subList(0, ll.get(i).size() - 1),
                    Integer.valueOf(ll.get(i).get(ll.get(i).size() - 1)));
        }

        if (temp.size() == 1) {
            Set<String> one = new HashSet<>();
            for (List<String> strings : temp.keySet()) {
                for (String string : strings) {
                    one.add(string);
                }
            }
            return one;
        }
//        System.out.println("temp:" + temp);
        Map<List<List<String>>, Double> relationRules = this.getRelationRules(temp);
//        System.out.println("relationRules" + relationRules);

        // 关联规则 、 存在数组
        // 把存在数组为选中
        // 遍历所有规则，存在数组中存在就把关联项选中

        Set<String> tmp = new HashSet<>();
        for (String ownTask : ownTasks) {
            tmp.add(ownTask);
        }
        for (List<List<String>> lists : relationRules.keySet()) {
            //lists.get(0) 为前置规则列表 lists.get(1) 为后置规则列表
            for (String list : lists.get(0)) {
                if (ownTasks.size() == 0) {
                    tmp.add(list);//如果本用户没有数据就按其他用户数据推荐（冷启动）
                } else {
                    for (String ownTask : ownTasks) {
                        if (list.equals(ownTask) == true) {
                            for (String s : lists.get(1)) {
                                tmp.add(s);
                            }
                        }
                    }
                }

            }

        }
        return tmp;
    }


    //根据频繁项集集合得到关联规则,Map存储的元素包含<前置,结果>、置信度
    public Map<List<List<String>>, Double> getRelationRules(Map<List<String>, Integer> frequentCollectionMap) {
        Map<List<List<String>>, Double> relationRules = new HashMap<List<List<String>>, Double>();
        Set<List<String>> keySet = frequentCollectionMap.keySet();


//        System.out.println();
        for (List<String> keyItems : keySet) {
            keyItems = new ArrayList<>(new HashSet<String>(keyItems));
            if (frequentCollectionMap.containsKey(keyItems)) {
                double countAll = frequentCollectionMap.get(keyItems);

                if (keyItems.size() >= 1) {
                    List<String> source = keyItems;
                    List<Set<String>> result = new ArrayList<Set<String>>();
                    buildSubSet(source, result);// 获得source的所有非空子集
                    for (Set<String> itemList : result) {
                        if (itemList.size() <= source.size()) {// 只处理真子集
                            List<String> otherList = new ArrayList<String>();//记录一个子集的补
                            for (String sourceItem : source) {
                                if (!itemList.contains(sourceItem)) {
                                    otherList.add(sourceItem);
                                }
                            }
                            List<String> reasonStr = new ArrayList<>();
                            List<String> resultStr = new ArrayList<>();
                            for (String item : itemList) {
                                reasonStr.add(item);
                            }
                            for (String item : otherList) {
                                resultStr.add(item);
                            }
                            if (frequentCollectionMap.containsKey(reasonStr)) {
                                double countReason = frequentCollectionMap.get(reasonStr);

                                double itemConfidence = countAll / countReason;// 计算置信度
                                if (itemConfidence >= CONFIDENCE) {
                                    List<List<String>> rule = new ArrayList<>();
                                    rule.add(reasonStr);
                                    if (resultStr == null) {
                                        resultStr = reasonStr;
                                    }
                                    rule.add(resultStr);
                                    relationRules.put(rule, itemConfidence);
                                }
                            }

                        }
                    }
                }
            }


        }
        return relationRules;
    }

    private void buildSubSet(List<String> sourceSet, List<Set<String>> result) {
        int n = sourceSet.size();
        //n个元素有2^n-1个非空子集
        int num = (int) Math.pow(2, n);
        for (int i = 1; i < num; i++) {
            String binary = Integer.toBinaryString(i);
            int size = binary.length();
            for (int k = 0; k < n - size; k++) {//将二进制表示字符串右对齐，左边补0
                binary = "0" + binary;
            }
            Set<String> set = new TreeSet<String>();
            for (int index = 0; index < sourceSet.size(); index++) {
                if (binary.charAt(index) == '1') {
                    set.add(sourceSet.get(index));
                }
            }
            result.add(set);
        }
    }
//
//
//    public static void main(String[] args) throws IOException {
//        // TODO Auto-generated method stub
//    /*String s1="i1";
//    int flag=s1.compareTo("I1");
//    System.out.println(flag);*/
//        //读取数据
//        Myfptree2 fpg = new Myfptree2();
//
//        List<List<String>> re = new ArrayList<>();
//        fpg.setRe(re);
//
//        LinkedList<LinkedList<String>> prerecords = fpg.readF1("C:/Users/86166/Desktop/1.txt");
//
////        Map<List<String>, Integer> temp = new HashMap<>();
////        for (int i = 0; i < re1.size(); i++) {
////            temp.put(re1.get(i).subList(0, re1.get(i).size() - 1), Integer.valueOf(re1.get(i).get(re1.get(i).size() - 1)));
////        }
////        Map<List<List<String>>, Double> relationRules = fpg.getRelationRules(temp);
////        System.out.println(relationRules);
//
//
//        List<List<String>> records = new ArrayList<>();
//        for (int i = 0; i < prerecords.size(); i++) {
//            records.add(new ArrayList<>());
//            for (int j = 0; j < prerecords.get(i).size(); j++) {
//                records.get(i).add(prerecords.get(i).get(j));
//            }
//        }
//
//        List<String> t = new ArrayList<>();
//        t.add("听力");
//        t.add("写作");
//        t.add("阅读");
//        t.add("翻译");
//        Set<String> strings = fpg.FPTreeLL(records, t);
//        System.out.println(strings);
//
//
//    }

}
